package com.algorithm.dp;

import java.util.Arrays;

/**
 * 给出一个数n,计算从0到n的每一个数转换为二进制时1的个数
 * 如: 给出15
 * 01 -> 00001 1个
 * 02 -> 00010 1个
 * 03 -> 00011 2个
 * 04 -> 00100 1个
 * 05 -> 00101 2个
 * 06 -> 00110 2个
 * 07 -> 00111 3个
 * 08 -> 01000 1个
 * 09 -> 01001 2个
 * 10 -> 01010 2个
 * 11 -> 01011 2个
 * 12 -> 01100 2个
 * 13 -> 01101 3个
 * 14 -> 01110 3个
 * 15 -> 01111 4个
 * 16 -> 10000 1个
 *
 * 归纳1: 15在2^3到2^4之间,最多4个1,最少1个1
 * 归纳2:在2^n~2^(n+1)区间之内,最多只会比2^(n-1) - 2^n 区间最多的多1个1
 * 归纳3:多出来1的肯定是奇数
 * 归纳4:某个数m中含1的个数i与m/2中含1的个数j之间的关系为: i = j | j+1,当是奇数(除不尽)时才+1
 * 故,转移方程为: dp[i] = dp[i/2] + i & 1 (与运算,奇数为1,偶数为0)
 *
 */
public class CountingBits {
    public static void main(String[] args) {
        int[] ints = countBits(32);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] countBits(int num) {
        if (num == 0){
            return new int[]{0};
        }else if (num == 1){
            return new int[]{0,1};
        }else if (num ==2){
            return new int[]{0,1,1};
        }
        int[] dp = new int[num+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 2; i <= num; i++) {
            dp[i] = dp[i/2] + (i & 1);
        }
        return dp;
    }
}
